package com.leetcode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No79
 * @description
 * @date 2021/1/26 下午4:10
 */
public class No79 {
    public static void main(String[] args) {
        char[][] board =
                {
                        {'A', 'B', 'C', 'E'},
                        {'S', 'F', 'C', 'S'},
                        {'A', 'D', 'E', 'E'}
                };
        String word1 = "ABCCED";
        String word2 = "SEE";
        String word3 = "ABCB";
        System.out.println(exist(board,word3));


    }

    public static boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0){
            return false;
        }
        if(word == null || word.length() == 0){
            return false;
        }
        int row = board.length;
        int col = board[0].length;
        boolean[][] isVisited = new boolean[row][col];
        int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
        for(int r = 0;r < row;r++){
            for(int c = 0;c < col;c++){
                if(hasWord(r,c,board,isVisited,word,0,direction)){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean hasWord(int r,int c,char[][] board,boolean[][] isVisited,String word,int pos,int[][] direction){
        if(pos == word.length()){
            return true;
        }
        if(r < 0 || r >= board.length || c < 0 || c >= board[0].length || isVisited[r][c] || board[r][c] != word.charAt(pos)){
            return false;
        }
        isVisited[r][c] = true;
        for(int[] d:direction){
            if(hasWord(r + d[0],c + d[1],board,isVisited,word,pos + 1,direction)){
                return true;
            }
        }
        isVisited[r][c] = false;
        return false;
    }
}